public class Text {
    class ListNode {
        ListNode next;
        int val;
    }

    public ListNode removeElements1(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

    public ListNode removeElements2(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode newnode = new ListNode();
        newnode.next = head;
        head = newnode;
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }

        }
        return head.next;
    }

    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }


    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        ListNode pre = head;
        head.next = null;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }

    //    给你单链表的头结点 head ，请你找出并返回链表的中间结点。
    public ListNode middleNode(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode flast = head;
        while (flast != null && flast.next != null) {
            flast = flast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k <= 0) {
            return null;
        }
        ListNode slow = head;
        ListNode flast = head;
        while (k-1>0){
            k--;
            flast=flast.next;
            if(flast==null){
                return null;
            }
        }
        while(flast.next!=null){
            flast=flast.next;
            slow=slow.next;
        }
        return slow;
    }

    public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
       if(head1==null){
           return head2;
       }
       if(head2==null){
           return head1;
       }
        ListNode nownode = new ListNode();
        ListNode tmp=nownode;
        while(head1!=null&&head2!=null){
            if(head1.val< head2.val){
                tmp.next=head1;
                head1=head1.next;
            }else{
                tmp.next=head2;
                head2=head2.next;
            }
            tmp=tmp.next;
        }
        if(head1==null){
            tmp.next=head2;
        }
        if(head2==null){
            tmp.next=head1;
        }
        return nownode.next;
    }

//    对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
//
//    给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
    public boolean chkPalindrome(ListNode head) {
        // write code here
        if(head==null){
            return false;
        }
        ListNode slow = head;
        ListNode flast = head;
        while (flast != null && flast.next != null) {
            flast = flast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;
        while(cur!=null){
            ListNode newnode=cur.next;
            cur.next=slow;
            slow=cur;
            cur=newnode;
        }
        while(head.next!=slow){
            if(slow.val!= head.val){
                return false;
            }
            slow=slow.next;
            head=head.next;
        }
        return true;
    }
}
